package main

import "fmt"

func main() {
	arr := []int{30, 20, 45, 22, 25, 24, 22, 90}
	//InsertSort(arr)
	//MaoPaoSort(arr)
	//SelectSort(arr)
	//QuickSort(arr)
	heapSort(arr)
	fmt.Println("llll:", arr)
}

func heap(arr []int, n int, i int) {
	maxIndex := i
	leftSonIndex := 2*i + 1
	rightSonIndex := 2*i + 2
	if leftSonIndex < n && arr[maxIndex] < arr[leftSonIndex] {
		maxIndex = leftSonIndex
	}
	if rightSonIndex < n && arr[maxIndex] < arr[rightSonIndex] {
		maxIndex = rightSonIndex
	}
	if maxIndex != i {
		arr[i], arr[maxIndex] = arr[maxIndex], arr[i]
		heap(arr, n, maxIndex)
	}
}
func makeHeap(arr []int) {
	n := len(arr)
	for i := n/2 - 1; i >= 0; i-- {
		heap(arr, n, i)
	}
}
func heapSort(arr []int) {
	n := len(arr)
	makeHeap(arr)
	for i := n - 1; i > 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		heap(arr, i, 0)
	}
}

// QuickSort 快速排序
// 30, 20, 45, 22, 25, 24, 22, 90
func QuickSort(arr []int) {
	if len(arr) <= 1 {
		return
	}
	pos := 0
	index := 0
	for i := 1; i < len(arr); i++ {
		if arr[i] < arr[pos] {
			index++
			arr[i], arr[index] = arr[index], arr[i]
		}
	}
	fmt.Println("index:", index)
	arr[pos], arr[index] = arr[index], arr[pos]
	fmt.Println(arr)
	QuickSort(arr[:index])
	QuickSort(arr[index+1:])

}

// InsertSort 插入排序
func InsertSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		for j := i; j-1 >= 0 && arr[j] < arr[j-1]; j-- {
			arr[j], arr[j-1] = arr[j-1], arr[j]
		}
	}
	fmt.Println(arr)
}

// MaoPaoSort 冒泡排序
func MaoPaoSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		for j := 0; j < len(arr)-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
	fmt.Println(arr)
}

// SelectSort 选择排序
func SelectSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		minIndex := i
		for j := i + 1; j < len(arr); j++ {
			if arr[minIndex] > arr[j] {
				minIndex = j

			}
		}
		arr[i], arr[minIndex] = arr[minIndex], arr[i]
	}
	fmt.Println(arr)
}
